Análisis y Diseño de Algoritmos                                                                                                      

Prof: Ing. Victor Garro

Asistente: Marco Elizondo Vargas

 

MEMORIA ESTÁTICA

 

TEMA: Estrucutras Estáticas Avanzadas

 

Arreglos Multidimensionales

 

A veces, es útil y necesario poder declarar arreglos de más de una dimensión. Esto se corresponde con

estructuras de datos muy utilizadas como matrices, tablas, cubos, etc. Formalmente, pueden ser declarados

como tipos y luego usarlo para declarar variables:

 

typedef <tipo> <nomTipo> [<valor_cte>]{[<valor_cte>]};

 

y posteriormente

 

<nomTipo> <nomVar>;

 

o bien, en la declaración de variables

 

<tipo> <nomVar> [<valor_cte>]{[<valor_cte>]};

 

Suponiendo declarados

 

const int DIM1=3;

const int DIM2=4;

 

Dichos arreglos se declaran de la siguiente forma1:

 

typedef int TMatriz[DIM1][DIM2];

 

y posteriormente

 

TMatriz m;

 

o bien, en la declaración de variables

 

int m[DIM1][DIM2];

 

El acceso a las componentes de una variable m de tipo TMatriz se realiza indicando sus índices entre corchetes.

 

Por ejemplo, m[i][j] o bien m[1][2]

 

Veamos como ejemplo una función que imprime una matriz cuadrada:

 

const int N = 4;

typedef int TMatriz[N][N];

void PintaMatriz(TMatriz m)

{

int i,j;

for(i=0;i<N;++i)

{

for(j=0;j<N;++j)

{

cout << m[i][j] << " ";

}

cout << endl;

}

}

 

Arreglos como Parámetros

 

Vista la definición anterior, void PintaMatriz(TMatriz m), es de esperar que el parámetro m no sea

modificado tras la ejecución del procedimiento, ya que se hizo un paso de parámetros por valor y no por

referencia. Sin embargo, pruebe a modificarlo de la siguiente manera

 

void PintaMatrizCuriosa(TMatriz m)

{

int i,j;

for(i=0;i<N;++i)

{

for(j=0;j<N;++j)

{

cout << m[i][j] << " ";

m[i][j] = 0;

}

cout << endl;

}

}

 

1 1 1 1

si m = 1 1 1 1 Pantalla

1 1 1 1

1 1 1 1

 

qué obtendremos tras ejecutar :

PintaMatrizCuriosa(m);

PintaMatrizCuriosa(m);

 

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

 

 

¿A qué se debe esto? ¿Qué está pasando? La respuesta es bastante sencilla. Debido a que los arreglos suelen

ocupar una gran cantidad de memoria, para evitar realizar grandes copias de memoria, por razones de eficiencia,

C++ SIEMPRE PASA LOS PARÁMETROS DE TIPO ARRAY POR REFERENCIA

por lo que debemos tener especial cuidado en no modificarlos, si no queremos que se produzcan efectos

extraños. Sin embargo, aun sabiendo esto, siempre pondremos el cualificador & para expresar que el paso es por

referencia cuando vayamos a modificar el array y no lo colocaremos cuando no lo vayamos a modificar. Así,

seremos coherentes con el resto de los tipos y mejoraremos la legibilidad de nuestro código evitando posibles

efectos laterales.

 

Arreglos y Funciones.

 

Supongamos ahora que pretendemos realizar una función para leer una matriz desde teclado. Parece

lógico, ya que vamos a generar un objeto nuevo a partir de ninguna información, implementar una función que

lea la matriz como la siguiente:

 

TMatriz LeeMatriz()

{

TMatriz m;

int i,j;

for(i=0;i<N;++i)

{

for(j=0;j<N;++j)

{

cout << "m[" << i << "][" << j << "] = ";

cin >> m[i][j];

}

}

return m;

}

 

Pasemos a compilar nuestro código y obtenemos el siguiente error:

`LeeMatriz' declared as function returning an array

 

¿Por qué? ¿A qué es debido?

 

La respuesta es la misma del caso anterior. Al igual que C++ pasa siempre por referencia los arreglos para

evitarse el tener que hacer una copia de memoria de una estructura que generalmente va a ser muy grande,

tampoco permite retornar arreglos en las funciones, por lo que, la única solución es añadir un parámetro de salida

(por referencia) para el resultado. Así pues, la función anterior, se transformará en el siguiente procedimiento:

 

void LeeMatriz(TMatriz &m)

{

int i,j;

for(i=0;i<N;++i)

{

for(j=0;j<N;++j)

{

cout << "m[" << i << "][" << j << "] = ";

cin >> m[i][j];

}

 

 

}

}

 

Cadenas de Caracteres (Strings).

 

Una cadena de caracteres no es más que un array de caracteres.

 

EN C++ TODAS LAS CADENAS DE CARACTERES DEBEN LLEVAR EL CARÁCTER 0 COMO

TERMINADOR.

 

Veamos a continuación una posible definición de cadenas de caracteres, así como la implementación de algunas

de las funciones más típicas de manejo de cadenas de caracteres.

 

// Zona de Declaración de Constantes

const char FINCAD = char(0);

const int MAXCAD = 20;

const int ENTER = '\n';

// Zona de Declaración de Tipos

typedef char TCadena[MAXCAD+1]; // MAXCAD caracteres + FINCAD

// Zona de Declaración de Cabeceras de PROC/FUNC

int LongitudCadena(TCadena s);

bool IgualCadena(TCadena s1, TCadena s2);

void CopiaCadena(TCadena s1, TCadena &s2); // s2 <- s1

void LeeCadena(TCadena &s);

void EscribeCadena(TCadena s);

// ...................... otras cosas ..........

// Implementación de PROC/FUNC

int LongitudCadena(TCadena s)

{

int i;

i=0;

while ((i<MAXCAD)3&& (s[i]!=FINCAD) )

{

++i;

}

return i;

}

bool IgualCadena(TCadena s1, TCadena s2)

{

int i;

i=0;

while ( (i<MAXCAD) && (s1[i]!=FINCAD) && (s2[i]!=FINCAD)

&& (s1[i]==s2[i]) )

{

 

 OJO: En cambio de char(0)también es válido el uso de '\0' para indicar el carácter constante 0

IMPORTANTE: Si bien esta comparación no es necesaria, es conveniente su uso para evitar errores producidos por datos

"corruptos".

 

++i;

}

return ( (i>=MAXCAD) || (s1[i]==s2[i]) );

}

void CopiaCadena(TCadena s1, TCadena &s2) // s2 <- s1

{

int i;

i=0;

while ( (i<MAXCAD) && (s1[i]!=FINCAD) )

{

s2[i]=s1[i];

++i;

}

s2[i]=FINCAD;

}

void LeeCadena(TCadena &s)

{

int i;

char c;

i=0;

c = cin.get();

while ( (i<MAXCAD) && (c!=ENTER) )

{

s[i]=c;

++i;

c = cin.get4(); // cin.get lee 1 carácter sin saltarse los de control

}

s[i] = FINCAD;

}

void EscribeCadena(TCadena s)

{

int i;

i=0;

while ( (i<MAXCAD) && (s[i]!=FINCAD) )

{

cout << s[i];

++i;

}

}

 

Entrada/Salida de Cadenas de Caracteres.

 

Aunque a lo largo de este tema se han visto funciones para leer y escribir cadenas de caracteres, C++,

al igual que la mayoría de los lenguajes de programación tienen funciones que permiten la entrada/salida de

cadenas de caracteres por pantalla/teclado.

La salida de caracteres en C++ se realiza de la misma forma que si fuera un tipo predefinido, es decir,

usando cout << cadena. (De hecho, ya hemos sacado cadenas constantes, entre comillas, por pantalla).

4 Se usa la función cin.get() porque cin ignora los espacios y caracteres de control.

 

En cuanto a la lectura de caracteres, tenemos varias opciones: una ya la hemos visto anteriormente con

el uso de la función LeeCadena. Otra posibilidad es el uso del método estándar de entrada, es decir, cin.

Usar cin para leer cadenas tiene el inconveniente de que se usa el espacio, tabulador y enter como separadores

de las cadenas, con lo cual podemos perder información. La tercera opción es el uso de la función

cin.getline, la cual nos permite leer una cadena de caracteres hasta un número máximo de caracteres o un

separador que nosotros indiquemos. Veamos el siguiente programa que hace uso de las tres formas y

posteriormente haremos un resumen de ellas.

 

#include <iostream.h>

#include <stdlib.h>

// Declaración de Constantes

const char FINCAD = char(0);

const int MAXCAD = 80;

const int ENTER = '\n';

// Declaración de Tipos

typedef char TCadena[MAXCAD+1]; // MAXCAD caracteres + FINCAD

// Declaración de Variables Globales

// Declaración de Cabeceras de PROC/FUNC

void LeeCadena(TCadena &s);

// Programa Principal

int main()

{

TCadena s1,s2,s3,s4;

cout << "Introduzca la Cadena: Hola Pepe";

cout << endl;

cin >> s1;

cin.ignore(MAXCAD,ENTER); // por si queda algo en le buffer

cout << "Introduzca la Cadena: Hola Pepe";

cout << endl;

cin.getline(s2,MAXCAD, ENTER);

cout << "Introduzca la Cadena: Hola Pepe";

cout << endl;

LeeCadena(s3);

cout << "La cadena leida con cin >> : " << s1 << endl;

cout << "La cadena leida con cin.getline : " << s2 << endl;

cout << "La cadena leida con LeeCadena : " << s3 << endl;

system("PAUSE");

return 0;

}

// Cuerpos de PROC/FUNC

void LeeCadena(TCadena &s)

{

int i;

char c;

i=0;

c = cin.get();

 

Dpto. Lenguajes y Ciencias de la Computación I.T.I. Informática Gestión/Sistemas. UMA. Curso 2002/03. 7

while ( (i<MAXCAD) && (c!=ENTER) )

{

s[i]=c;

++i;

c = cin.get();

}

s[i] = FINCAD;

}

=============================== PANTALLA ===============================

Introduzca la Cadena: Hola Pepe

Hola Pepe

Introduzca la Cadena: Hola Pepe

Hola Pepe

Introduzca la Cadena: Hola Pepe

Hola Pepe

La cadena leida con cin >> : Hola

La cadena leida con cin.getline : Hola Pepe

La cadena leida con LeeCadena : Hola Pepe

Presione cualquier tecla para continuar. . .

==========================================================================

 

Uso de cin

 

El uso de cin de manera estándar tiene 2 problemas:

·  La cadena es leída hasta que se encuentre ENTER, espacio o tabulador. Esto hace que se puedan

perder datos, por ejemplo, si una persona tiene dos nombres, al usar cin >> nombre, se estaría

perdiendo el segundo de ellos.

·  Lo que no se ha leído, se queda almacenado en el buffer de teclado, por lo que si no queremos que

se mezcle con otras lecturas debemos ignorarlo. Ese es el motivo de la sentencia

cin.ignore(MAXCAD,ENTER), que lo que hace es ignorar lo que haya en el buffer de

teclado hasta un máximo de caracteres o un separador (ENTER en nuestro caso).

 

Uso de cin.getline(TCadena &cadena, int max_caracteres, char separador)

 

Esta función será la que utilicemos normalmente (salvo que se diga explícitamente que no se puede usar) para

leer cadenas de caracteres, ya que, aunque debemos pasarle como parámetros tanto el número máximo de

caracteres como el separador de cadenas, la llamada cin.getline(s, MAXCAD, ENTER) tiene

exactamente el mismo funcionamiento que la función LEER definida para el pseudolenguaje.

 

Uso de la Función LeeCadena

 

El uso de esta función es equivalente a la anterior, lo que se hace es leer carácter a carácter. La podremos usar

siempre, aunque normalmente, la utilizaremos cuando se pida explícitamente, es decir, cuando se diga que no se

puede usar el cin.getline.

 

Tipos Enumerados.

 

Aunque los tipos de datos predefinidos son teóricamente adecuados para cualquier propósito, existe un

gran número de situaciones en las cuales es conveniente que el programador pueda definir sus propios tipos de

manera que especifique literalmente los valores que una variable de ese tipo puede tomar. Estos son los

llamados tipos enumerados.

Si , por ejemplo, quisiéramos definir una variable para que represente una situación de un problema en

el que hay cinco posibles colores, (rojo, amarillo, verde, azul y naranja) podríamos hacer lo siguiente:

 

const int rojo = 0;

const int amarillo = 1;

const int verde = 2;

const int azul = 3;

const int naranja = 4;

int color1, color2;

 

Sin embargo, en C++ podemos definir un nuevo tipo ordinal que conste de esos cinco valores

exactamente:

 

enum TColor

{

negro, azul, rojo, verde, amarillo, azul, rosa, negro

};

o bien 5

typedef enum

{

negro, azul, rojo, verde, amarillo, azul, rosa, negro

} TColor;

Tcolor color1, color2;

 

La declaración de un tipo de esta índole consiste en asociar a un identificador una enumeración de los

posibles valores que una variable de ese tipo puede tomar, por lo que una misma constante no puede aparecer en

dos definiciones de tipo.

Formalmente, la definición de un enumerados en formato BNF sería:

 

<TipoEnumerado>::= typedef enum '{ ' < literal > {, <literal > } '}' <nomTipo>;

| enum <nomTipo> '{ ' < literal > {, <literal > } '}';

donde

<literal>::= <letra> { [ <letra> | <dígito>] }

 

OJO: Si bien no es necesario en C++ el uso de typedef para declarar tipos enumerados, lo colocaremos para indicar

que se está definiendo un tipo nuevo y por coherencia con el resto de los tipos.

 

El orden de los valores de estos nuevos tipos declarados por el programador será aquel en que aparecen

dentro de la lista de enumeración de los elementos del tipo. El tipo enumerado es también un tipo escalar y

ordinal, por lo que permite calcular su ordinal y valor.

Expresión Valor Expresión Valor

int(rojo) 0 TColor(0) Rojo

int(amarillo) 1 Tcolor(1) Amarillo

int(verde) 2 TColor(2) Verde

int(azul) 3 TColor(3) Azul

Int(naranja) 4 TColor(4) Naranja

 

Sin embargo, al no estar definidos sobre ellos las operaciones de suma y resta, ¿cómo obtener su sucesor o

predecesor? La solución consiste en la definición de una función que calcule su ordinal, incremente este, y

posteriormente lo retorne a enumerado. Veamos un ejemplo:

 

TColor SUC (TColor c)

{

int ord;

TColor res;

ord = int(c) + 1;

res = TColor(ord);

return res;

}

TColor PRED (TColor c)

{

int ord;

TColor res;

ord = int(c) - 1;

res = TColor(ord);

return res;

}

 

Esta solución, tiene el problema de que es responsabilidad del usuario el no utilizarlas sobre el primer o último

elemento, pero tiene la ventaja de que permite también, que el implementador realice un modelo circular de

sucesión como el siguiente:

 

const int MAX_COLOR = 4;

TColor SUC (TColor c)

{

int ord;

TColor res;

ord = (int(c) + 1)% MAX_COLOR;

res = TColor(ord);

return res;

}

TColor PRED (TColor c)

{

int ord;

TColor res;

ord = (MAX_COLOR + int(c) - 1) % MAX_COLOR ;

res = TColor(ord);

return res;

}

 

Otro problema del uso de enumerados reside en que no pueden ser leídos y escritos directamente por

pantalla/teclado, sin embargo, no es difícil realizar funciones de conversión entre enumerados y cadenas o

viceversa. Veamos el siguiente ejemplo que muestra por pantalla el color seleccionado por un usuario.

 

#include <iostream.h>

#include <stdlib.h>

#include <ctype.h>

// Zona de Declaración de Constantes

const char FINCAD = char(0);

const int MAXCAD = 20;

const int ENTER = '\n';

// Zona de Declaración de Tipos

typedef char TCadena[MAXCAD+1]; // MAXCAD caracteres + FINCAD

typedef enum

{ negro, rojo, verde, amarillo, azul, rosa

} TColor ;

// Declaración de Cabeceras de PROC/FUNC

bool IgualCadena(TCadena s1, TCadena s2);

void CopiaCadena(TCadena s1, TCadena &s2); // s2 <- s1

TColor SUC (TColor c); // Función Sucesor

void Color_a_Cadena(TColor c, TCadena &s);

void Cadena_a_Color(TCadena s, TColor &c, bool &ok);

// Programa principal

int main()

{

TColor col;

TCadena s;

bool ok;

do

{

cout << "Introduzca un Color de entre : " << endl;

for(col=negro;col<=rosa;col=SUC(col))

{

Color_a_Cadena(col,s);

cout << " " << s << endl;

}

cin >> s;

Cadena_a_Color(s,col,ok);

if (ok)

{

cout << "Ha seleccionado ... " << s << endl;

}

else

{

cout << "Color Erroneo ... " << endl;

}

} while (!ok);

system("PAUSE");

return 0;

}

// Cuerpos de PROC/FUNC

TColor SUC (TColor c)

{

int ord;

TColor res;

ord = int(c) + 1;

res = TColor(ord);

return res;

}

void Color_a_Cadena(TColor c, TCadena &s)

{

switch (c)

{

case negro: CopiaCadena("negro",s);

break;

case rojo: CopiaCadena("rojo",s);

break;

case verde: CopiaCadena("verde",s);

break;

case amarillo: CopiaCadena("amarillo",s);

break;

case azul: CopiaCadena("azul",s);

break;

case rosa: CopiaCadena("rosa",s);

break;

}

}

void Cadena_a_Color(TCadena s, TColor &c, bool &ok)

{

TCadena s2;

c = negro;

ok= false;

while ( (!ok) && (c<=rosa) )

{

Color_a_Cadena(c,s2);

if (IgualCadena(s,s2))

{

ok = true;

}

else

{

c = SUC(c);

}

}

}

bool IgualCadena(TCadena s1, TCadena s2)

{

int i;

i=0;

while ( (i<MAXCAD) && (s1[i]!=FINCAD) && (s2[i]!=FINCAD)

&& (toupper(s1[i])==toupper(s2[i])) )

{

++i;

}

return ( (i>=MAXCAD) || (s1[i]==s2[i]) );

}

void CopiaCadena(TCadena s1, TCadena &s2) // s2 <- s1

{

int i;

i=0;

while ( (i<MAXCAD) && (s1[i]!=FINCAD) )

{

s2[i]=s1[i];

++i;

}

s2[i]=FINCAD;

}